[LeetCode]1.TwoSum(Python实现) |
您所在的位置:网站首页 › leetcode 3 python › [LeetCode]1.TwoSum(Python实现) |
1.题目描述
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用
示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
2.代码实现
1. 方法一: [分析]: 自然而然的想法,首先用for循环对nums数组进行遍历,从第一个元素开始,然后再查找数组中有没有target-nums[i]这个元素;有的话,则返回当前元素下标与另一个元素的下标,作为结果输出。代码如下: class Solution(object): def twoSum(self, nums, target): for i in range(len(nums)): if (target - nums[i]) in nums: return [i,nums.index(target - nums[i])]然而,实际编程过程中出现了这么一个问题,Python提供的list.index(value,from,to) “左闭右开区间”,在不指定from,to的时候,该方法默认返回数组中第一次出现该value的index值,在case([3,4,2],6)中,应该输出[1,2],而按照前面的思路,直接输出了[0,0],这显然是不正确的,于是直接的想法是比较两个元素对应的index是否相等,是的话,就pass掉,代码改为如下: class Solution(object): def twoSum(self, nums, target): for i in range(len(nums)): if (target - nums[i]) in nums: idx = nums.index(target - nums[i]) if i == idx: pass else: return [i,idx]然而,还是出了问题,比如说在case([0,3,4,0],0)中,应该输出[0,3],但上面方法却输出了null,我的一个新思路是,是不是应该在查找 target - nums[i] 元素的index时,设定一个from值,应该从当前元素的后面一个开始查找元素,于是代码改为如下: class Solution(object): def twoSum(self, nums, target): for i in range(len(nums)): if (target - nums[i]) in nums: idx = nums.index(target - nums[i],i+1) # 这里设置了from return [i,idx]如此一来,貌似解决了case([0,3,4,0],0)的问题,结果运行的时候,case([3,4,2],6)发生运行错误,程序在执行第一个元素的时候,查找到nums里有(6-3),但是在搜index的时候,由于设置了搜索范围,查找不到元素3的索引,可谓是顾此失彼。 没办法,只能继续思考,如何解决这个两难的问题,突然一个想法产生,我何不对nums数组进行切片呢?即我在判断数组中是否包含 target - nums[i] 元素时,不应该对整个数组进行查找,而是应该对num[i+1:]进行查找,代码如下: class Solution(object): def twoSum(self, nums, target): for i in range(len(nums)): num = target - nums[i] if num in nums[i+1:]: return [i, nums.index(num,i+1)] 最终程序测试结果: 2.方法二: 先看代码: class Solution(object): def twoSum(self, nums, target): nums_dict = {} for i, num in enumerate(nums): if num in nums_dict: return [nums_dict[num], i] else: nums_dict[target - num] = i 代码思路:这个算法的核心思想是构造一个字典,字典用来存储当前元素完成target需要的元素值作为key,当前元素的index作为value。然后遍历过程中进行判断,当前元素是不是属于我想要的元素,是的话,直接输出 [字典中该元素的下标,当前遍历元素下标] 思考:这个算法快在哪里? 从时间复杂度的角度来看,第一层for循环是O(n),字典采用的是hash函数的结构,所以在 x in dict的查找过程中,时间复杂度为O(1),而这里没用到index查询,而是直接获取value值,而字典的Get Item的复杂度也是O(1),所以整个算法的时间复杂度为O(n),不过这里的空间复杂度是O(n),用空间换时间。 最终程序测试结果: |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |